
import java.util.LinkedList;
import java.util.List;

// Definition for binary tree
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}


public class Solution {
    public static void main(String[] args) {
	TreeNode[] n = new TreeNode[args.length + 1];
	for (int i = 0; i < args.length; ++i) {
		if (!args[i].equals("#"))
			n[i+1] = new TreeNode(Integer.parseInt(args[i]));
		else
			n[i+1] = null;
	}

	for (int i = 2; i < args.length + 1; ++i) {
		if (n[i] == null)
			continue;

		if ((i & 1) == 0)
			n[i>>1].left = n[i];
		else
			n[i>>1].right = n[i];
	}

	Solution s = new Solution();
	s.flatten(n[1]);

	s.print(n);
    }

    public void flatten(TreeNode root) {
        if (root == null)
            return;

        flatternHelper(root); 
    }
 
    private void print(TreeNode[] n) {
	for (int i = 1; i < (n.length-1)/2; ++i) {
		if (n[i] == null)
			continue;
	
		System.out.print(n[i].val + " ");

		if (n[i<<1] != null)
			System.out.print(n[i<<1].val + " ");
		else
			System.out.print("#");

		if (n[(i<<1)+1] != null)
			System.out.print(n[(i<<1)+1].val);
		else
			System.out.print("#");

		System.out.println();
	}
    }
   
    private List<TreeNode> flatternHelper (TreeNode root) {
        if (root.left == null && root.right == null) {
            List<TreeNode> res = new LinkedList<TreeNode>();
            res.add(root);
            res.add(root);
            return res;
        }
        
        List<TreeNode> left = null, right = null;
        TreeNode cur = root;
        if (root.left != null) {
            left = flatternHelper (root.left);
        }
        
        if (root.right != null) {
            right = flatternHelper (root.right);
        }
       
	if (left != null) {
	    cur.right = left.get(0);
            cur = left.get(1);
	} 

	if (right != null) {
            cur.right = right.get(0);
            cur = right.get(1);
	}

        List<TreeNode> res = new LinkedList<TreeNode>();
        res.add(root);
        res.add(cur);
        return res;
    }
}
